1. Field of the Invention
The present invention relates generally to host adapters that interface two I/O buses, and more particularly, to dequeuing blocks from queues for host adapters.
2. Description of Related Art
Hardware control blocks, sometimes called sequencer control blocks, or SCSI command blocks (SCBs), are typically used for transferring information between a software host adapter device driver in a host computer system 106 and a host adapter integrated circuit 120 that controls operations of one or more peripheral devices. Those of skill in the art know methods for queuing SCBs.
For example, see copending and commonly assigned U.S. patent application Ser. No. 07/964,532 entitled xe2x80x9cIntelligent SCSI Bus Host Adapter Integrated Circuit,xe2x80x9d of Craig A. Stuber et al. filed on Oct. 16, 1992, which is incorporated wherein by reference in its entirety. See also, commonly assigned U.S. Pat. No. 5,625,800 entitled xe2x80x9cA Sequencer Control Block Array External To A Host Adapter Integrated Circuitxe2x80x9d of Michael D. Brayton et al. filed on Jun. 30, 1994; and also U.S. Pat. No. 5,564,023 entitled xe2x80x9cMethod for Accessing A Sequencer Control Block By A Host Adapter Integrated Circuitxe2x80x9d of B. Arlen Young issued on Oct. 8, 1996, each of which is incorporated herein by reference in its entirety.
A prior art method for queuing SCBs for a system 100, which included a processor 105 in a host system 106 and a host adapter device 120 with a sequencer 125, used a one-dimensional linked list SCB queue 160 within a SCB array 155 in random access memory 150. A device driver executing on microprocessor 105 managed host adapter 120 using SCBs, e.g., hardware control blocks, in SCB queue 160. Each SCB in SCB queue 160 had a next queue site field Q_NEXT, sometimes referred to as field Q_NEXT, which was used to store a SCB site pointer that addressed the next SCB storage site in SCB queue 160.
Queue 160 was delimited by head pointer 141 and tail pointer 142. Head pointer 141 was the number of the site in SCB array 155 storing the SCB to be executed next, and tail pointer 142 was the number of the site in SCB array 155 containing the last SCB transferred from host system 106. Next queue site field Q_NEXT in the site addressed by tail pointer 142 had an invalid value that was used to identify the SCB as the last in queue 160 in addition to tail pointer 142.
When queue 160 was empty, head pointer 141 was an invalid value. When a new SCB was transferred from host system 106 to SCB array 155, head pointer 141 and tail pointer 142 were changed to point to the storage site of the new SCB, i.e., were changed to valid values. Field Q_NEXT in the new SCB was set to an invalid value to indicate that the SCB was the last SCB in queue 160.
As each new SCB was transferred from host system 106 to SCB array 155, tail pointer 142 was used to identify the end of queue 160. Field Q_NEXT in the SCB pointed to by tail pointer 142 was changed to point to the newly transferred SCB, and then tail pointer 142 was changed to point to the storage site of the newly transferred SCB.
A valid head pointer 141 indicated that one or more commands were available for transfer to one or more SCSI targets. The next target selected was specified by information within the SCB addressed by head pointer 141. Host adapter 120 removed the SCB at the head of queue 160 for execution and selected the specified target. Head pointer 141 was changed to point to the next SCB in queue 160, i.e., the value in field Q_NEXT of the SCB removed for execution was copied to head pointer 141. When the selection process was complete, the command contained within the SCB was transferred to the target.
SCBs in queue 160 were executed and targets were selected in the order that the SCBs were received from host system 106. This order is shown by the dashed line in FIG. 1. SCBs were not inserted or removed from the middle of queue 160.
Other methods are known for queuing SCSI command blocks for a SCSI target. See for example, U.S. Pat. Nos. 5,938,747 and 6,006,292, each of which is incorporated herein by reference. Independent of the method used to manage SCBs in a queue within the SCB array, SCBs are executed and targets are selected in the order that the SCBs were received from host system 106. SCBs are not inserted into or removed from the middle of the queue within the SCB array.
According to an embodiment of this invention, a two-dimensional command block queue, stored in a memory of a host adapter, includes a plurality of command blocks in a first linked list, sometimes called a common queue of command blocks. In one embodiment, the first linked list is delimited by a stored head pointer and a stored tail pointer. In another embodiment, only the head pointer is stored.
The two-dimensional command block queue further includes another plurality of command blocks in a second linked list, sometimes called a string. There is a specific relationship between the first and second linked lists. Specifically, one and only one of the command blocks in the string is included in the plurality of command blocks in the first linked list. Only a tail pointer delimits the string.
A tail pointer list that is stored in a host adapter memory includes the tail pointer to a tail command block in the second linked list. The tail pointer is positioned in the tail pointer list so that the storage location is indexed using a device identifier associated with each of the command blocks in the string.
A string head pointer list is also stored in a host adapter memory, which, in one embodiment, is formed from a register in each of a plurality of memories. Following dequeuing the string from the two-dimensional command block queue, a pointer to the one and only one command block of the string that was in the common queue is included in the string head pointer list. The string is dequeued from the two-dimensional command block queue for processing of the string.
Following the dequeuing of the string from the two-dimensional command block queue for processing, the tail pointer to the string is not changed in the tail pointer list. This allows any new SCBs to be appended to the end of the string, while the string is being processed. This allows streaming of new SCBs to an I/O device that had previously been selected and is still connected to the host adapter.
This feature can provide a significant performance advantage, because even though the string is not included in the two-dimensional command block queue, the presence of the tail pointer in the tail pointer list makes it appear as though the string still was in the two-dimensional queue. Consequently, the same process is used to append new SCBs to a string independent of whether the string is included in the two-dimensional command block queue.
In one embodiment, memory in which the two-dimensional command block queue is stored is a first memory and the two-dimensional command block queue is stored in a command block array in the first memory. The first memory is internal to the host adapter in one embodiment, external to the host adapter in another embodiment, and includes both internal and external memory in still another embodiment. The various pointers and lists are stored in a second memory that is different from the first memory. The second memory can comprise multiple memory units.
The two-dimensional command block execution queue is a target command block execution queue if a host adapter is functioning in an initiator mode. Conversely, the two-dimensional command block execution queue is an initiator command block execution queue if the host adapter is functioning in a target mode. The host adapter can have both a target command block execution queue and an initiator command block execution queue if the host adapter functions in both initiator and target modes. In addition, this two-dimensional queue with the dequeuing is used to manage other functions of the host adapter associated with information transfer over the I/O bus.
In another embodiment of this invention, a structure includes a two-dimensional queue. The two dimensional queue includes a common linked list of command blocks having a common head command block and a common tail command block, and a string comprising a linked list of command blocks having a string head command block and a string tail command block. Only the string head command block is included in the common linked list of command blocks.
The structure also includes: a common queue head pointer to the common head command block; a common queue tail pointer to the common tail command block; a string tail pointer list including a tail pointer to the string tail command block; and a string head pointer list. Following dequeuing the string from the two-dimensional queue, a pointer to the string head command block is included in the string head pointer list.
The common linked list contains a maximum of one command block for the string. The string contains only command blocks for a single device.
A method of managing a two-dimensional queue includes delimiting a first string of command blocks in the two-dimensional queue with a string tail pointer. The string tail pointer addresses a tail command block in the string. The string is coupled to another string in the two-dimensional queue by a link.
The method also includes dequeuing the first string from the two-dimensional queue by removing the link and leaving the string tail pointer unchanged.
To append a new command block, it is first determined whether a string for a device specified in the new command block exists. The new command block is appended to a tail of the first string upon finding that the string exists and is the first string. The new command block is appended to a tail of a common queue upon finding that the string does not exist.
In another embodiment, a method includes dequeuing a string from a two dimensional command block queue. Thus, the string is a dequeued string and the dequeued string includes a linked list of command blocks. A new command block is appended to the dequeued string. The method further includes processing the dequeued string, completing the processing of the dequeued string and appending unprocessed commands blocks in the dequeued string to the two-dimensional command block queue.
A host adapter sequencer is used in the appending operations. Another host adapter sequencer is used in the processing and completing operations.
Hence, still another method of managing command blocks uses a first sequencer to manage a two-dimensional command block queue including a plurality of strings of command blocks where each string of command blocks is a linked list. A second sequencer is used to process a string of command blocks dequeued from the two-dimensional command block queue. The first sequencer is used to append a command block to the string of command blocks dequeued from the two-dimensional command block queue.
In one embodiment of the invention, a system includes:
a two-dimensional queue comprising:
a plurality of command blocks in a first linked list; and
another plurality of command blocks in a second linked list, where only one of the another plurality of command blocks is included in the plurality of command blocks in the first linked list; and
a memory coupled to the two-dimensional queue, the memory including:
a tail pointer to a tail command block in the second linked list wherein the tail pointer is an only delimiter for the second linked list.
a tail pointer list including the tail pointer to the tail command block in the second linked listed; and
a string head pointer list wherein following dequeuing the another plurality of command blocks in the second linked list from the two-dimensional queue, a pointer to the only one of the another plurality of command blocks is included in the string head pointer list.
The memory also includes a head pointer to a head command block in the first linked list and a tail pointer to a tail command block in the first linked list